package util;

import java.util.ArrayList;
import java.util.List;

public class StrikeCountString {
    private static int STRIKE_COUNT = 4;

    private static String[] KNOWN = new String[] { "02", "212", "0012" };

    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();

        for (int i = 0; i < Math.pow(3, STRIKE_COUNT); i++) {
            StringBuilder builder = new StringBuilder();
            int a = i;
            for (int j = 0; j < STRIKE_COUNT; j++) {
                builder.insert(0, a % 3);
                a = a / 3;
            }
            String strike = builder.toString();
            boolean isKnown = false;
            for (String known : KNOWN) {
                isKnown = isKnown || strike.contains(known);
            }
            if (!isKnown)
                list.add(strike);
        }

        String lastStrike = list.get(0);
        list.remove(0);
        System.out.print(lastStrike);
        while (list.size() > 0) {
            boolean found = false;
            for (int charsCount = STRIKE_COUNT - 1; charsCount > 0; charsCount--) {
                int index = findNext(lastStrike, list, charsCount);
                if (index >= 0) {
                    found = true;
                    lastStrike = list.get(index);
                    list.remove(index);
                    System.out.print(lastStrike.substring(charsCount));
                    break;
                }
            }
            if (!found) {
                System.out.println();
                lastStrike = list.get(0);
                list.remove(0);
                System.out.print(lastStrike);
            }
        }

        System.out.println();
    }

    private static int findNext(String strike, List<String> list, int charsCount) {
        String subStrike = strike.substring(strike.length() - charsCount);
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).startsWith(subStrike))
                return i;
        }
        return -1;
    }
}
